package pro.softzhang.algo.lc400;

public class LC416_PartitionEqualSubsetSum {
    public static void main(String[] args) {

    }

    static class Solution {
        public boolean canPartition(int[] nums) {
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }

            if (sum % 2 == 1) {
                return false;
            }

            return subsetSum(nums, sum / 2);
        }

        private boolean subsetSum(int[] nums, int target) {
            Boolean[][] dp = new Boolean[nums.length + 1][target + 1];
            return doSubsetSum(nums, dp, nums.length, target);
        }

        private boolean doSubsetSum(int[] nums, Boolean[][] dp, int i, int j) {
            if (dp[i][j] == null) {
                if (j == 0)
                    dp[i][j] = true;
                else if (i == 0)
                    dp[i][j] = false;
                else {
                    dp[i][j] = doSubsetSum(nums, dp, i - 1, j);
                    if (!dp[i][j] && j >= nums[i - 1]) {
                        dp[i][j] = doSubsetSum(nums, dp, i - 1, j - nums[i - 1]);
                    }
                }
            }
            return dp[i][j];
        }
    }
}
